package cxydmmszl.chapter04.t065;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 最长公共子序列问题
 * <li style="color: green;">Desc</li>
 * 给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。
 * <li style="color: green;">Input</li>
 * 输出包括两行，第一行代表字符串str1，第二行代表str2。
 * (1≤length(str1),length(str2)≤5000)
 * <li style="color: green;">Output</li>
 * 输出一行，代表他们最长公共子序列。如果公共子序列的长度为空，则输出-1。
 * <li style="color: blue;">Link</li> CD31
 *
 * @author habitplus
 * @since 2021-10-08 21:29
 */
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();

        String ans = lcse(str1, str2);
        if (ans == null || ans.length() == 0){
            System.out.println("-1");
        } else {
            System.out.println(ans);
        }

    }

    private static String lcse(String str1, String str2) {
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) {
            return "";
        }

        char[] ch1 = str1.toCharArray();
        char[] ch2 = str2.toCharArray();
        int len1 = ch1.length;
        int len2 = ch2.length;

        int[][] dp = getDp(ch1, ch2);

        // 逆向动态规划，进行路径还原
        int l = len1 - 1;
        int r = len2 - 1;
        char[] res = new char[dp[l][r]];
        int k = dp[l][r] - 1;
        while (k >= 0) {
            if (r > 0 && dp[l][r] == dp[l][r - 1]) {
                r--;
            } else if (l > 0 && dp[l][r] == dp[l - 1][r]) {
                l--;
            } else {
                res[k--] = ch1[l];
                l--;
                r--;
            }
        }
        return new String(res);
    }

    private static int[][] getDp(char[] chs1, char[] chs2) {
        int n = chs1.length;
        int m = chs2.length;
        int[][] dp = new int[n][m];

        dp[0][0] = chs1[0] == chs2[0] ? 1 : 0;

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], chs1[i] == chs2[0] ? 1 : 0);
        }

        for (int j = 1; j < m; j++) {
            dp[0][j] = Math.max(dp[0][j-1], chs1[0] == chs2[j] ? 1 : 0);
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                if (chs1[i] == chs2[j]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + 1);
                }
            }
        }

        return dp;
    }
}
